﻿/************************************************************************
 * SMLib - State Model Library
 * Copyright (C) 2012-2013 Ali Khalili (khalili_DOT_ir_@SIGN_gmail_DOT_com)
 * **********************************************************************
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License (LGPL) published 
 * by the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version. This program is distributed without any
 * warranty. See the GNU Lesser General Public License for more details. 
 * ***********************************************************************
 * File         :     SMLib\Automata\DFA\DFA_Generator.cs
 * Description  :     Random DFA Generator (to test and evaluate DFA learning algorithms)
 * Change log   :     -16 April:  First version
 * To Do        :     -I have not tested it yet!
 ************************************************************************/
using System;
using System.Collections.Generic;
using SMLib.Automata.Base;

namespace SMLib.Automata.DFA
{
    /// <summary>
    /// Generate a random DFA
    /// </summary>
    public class DFA_Generator
    {
        int numberOfStates;
        int numberOfSigma;
        double acceptanceRate;

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="machineName">name of machine</param>
        /// <param name="numberOfStates">number of states</param>
        /// <param name="numberOfSigma">number of input alphabet</param>
        /// <param name="acceptanceRate">percentage of accepting states, between zero and one</param>
        public DFA_Generator(string machineName, int numberOfStates, int numberOfSigma, double acceptanceRate)
        {
            this.numberOfSigma = numberOfSigma;
            this.acceptanceRate = acceptanceRate;
            this.numberOfStates = numberOfStates;
            rnd = new Random();
        }

        Random rnd;

        public DFA GenerateRandomMachine()
        {
            Alphabet sigma = new Alphabet();
            for (int i = 0; i < numberOfSigma; i++)
            {
                sigma.AddSymbol(new StringSymbol("a" + i));
            }
            DFA myDFA = new DFA(sigma);

            for (int i = 0; i < numberOfStates; i++)
            {
                DFA.DFA_State st = new DFA.DFA_State("S" + i);
                myDFA.AddState(st);
            }

            for (int i = 0; i < numberOfStates; i++)
            {
                DFA.DFA_State mySt = (DFA.DFA_State)myDFA[i];
                for (int j = 0; j < numberOfSigma; j++)
                {
                    DFA.DFA_Transition tr = new DFA.DFA_Transition(sigma[j]);
                    tr.SetDestination((DFA.DFA_State)myDFA[rnd.Next(numberOfStates)]);
                    mySt.Transitions.Add(tr);
                }
            }

            for (int i = 0; i < acceptanceRate * numberOfStates; )
            {
                DFA.DFA_State mySt = (DFA.DFA_State)myDFA[rnd.Next(numberOfStates)];
                if (!mySt.isAccepting)
                {
                    mySt.isAccepting = true;
                    i++;
                }
            }
            return myDFA;
        }

        public DFA GenerateRandomMachine(double pr)
        {
            //Alphabet sigma = new Alphabet();
            //for (int i = 0; i < numberOfSigma; i++)
            //{
            //    sigma.AddSymbol(new StringSymbol("a" + i));
            //}
            DFA myDFA = new DFA(null);
            for (int i = 0; i < numberOfStates; i++)
            {
                DFA.DFA_State st = new DFA.DFA_State("S" + i);
                myDFA.AddState(st);
            }
            //int total = numberOfStates * (numberOfStates - 1);
            //double pr = ((double)(NumberOfTrans)) / total;
            Random r = new Random();

            for (int i = 0; i < numberOfStates; i++)
            {
                for (int j = 0; j < numberOfStates; j++)
                {
                    if (i == j)
                        continue;

                    double myRnd = r.NextDouble();
                    if (myRnd < pr)
                    {
                        DFA.DFA_State mySt = (DFA.DFA_State)myDFA[i];
                        DFA.DFA_Transition tr = new DFA.DFA_Transition(new StringSymbol("?"));
                        tr.SetDestination((DFA.DFA_State)myDFA[j]);
                        mySt.Transitions.Add(tr);
                    }
                }
            }

            for (int i = 0; i < acceptanceRate * numberOfStates; )
            {
                DFA.DFA_State mySt = (DFA.DFA_State)myDFA[rnd.Next(numberOfStates)];
                if (!mySt.isAccepting)
                {
                    mySt.isAccepting = true;
                    i++;
                }
            }
            return myDFA;
        }
    }
}
